#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

struct suffix_array
{
	typedef std::vector<int> & v_ref;
	typedef std::vector<int> const & v_cref;
	typedef std::string const & s_cref;

	struct suffix_cmp
	{
		suffix_cmp(v_cref rank, int const & gap, int const & len)
			: rank(rank), gap(gap), len(len) {}

		bool operator()(int i, int j)
		{
			if (rank[i] != rank[j]) return rank[i] < rank[j];
			return (i + gap < len && j + gap < len) ?
						(rank[i + gap] < rank[j + gap]) : i > j;
		}

	private:
		v_cref rank;
		int const & gap;
		int const & len;
	};

	suffix_array(s_cref s, v_ref sa, v_ref rank, v_ref height)
		: s(s), sa(sa), rank(rank), height(height)
	{
		tmp_rank.resize(rank.size());
	}

	void build_suffix_array()
	{
		int n = s.size();
		for (int i = 0; i < n; i++) { sa[i] = i; rank[i] = s[i]; }
		for (int gap = 1; ; gap *= 2) {
			suffix_cmp cmp(rank, gap, n);
			std::sort(sa.begin(), sa.begin() + n, cmp);
			for (int i = 0; i < n-1; i++)
				tmp_rank[i + 1] = tmp_rank[i] + cmp(sa[i], sa[i + 1]);
			for (int i = 0; i < n; i++) rank[sa[i]] = tmp_rank[i];
			if (tmp_rank[n - 1] == n - 1) break;
		}
	}

	void build_lcp()
	{
		int n = s.size();
		for (int i = 0, k = 0; i < n; i++)
			if (rank[i] != n-1) {
				for (int j = sa[rank[i] + 1]; s[i + k] == s[j + k]; k++);
				height[rank[i]] = k;
				if (k) k--;
			}
	}

private:
	s_cref s;
	v_ref sa; // suffix array
	v_ref rank;
	v_ref height; // lcp array, longest common prefix array
	std::vector<int> tmp_rank;
};

int main()
{
	std::string s;
	std::cin >> s;
	std::vector<int> sa(s.size());
	std::vector<int> rank(s.size());
	std::vector<int> height(s.size());
	suffix_array suffix(s, sa, rank, height);
	suffix.build_suffix_array();
	suffix.build_lcp();

	std::cout << s << '\n';
	for (auto i : sa)
		std::cout << s.substr(i, s.size() - i) << '\n';

	std::cout << "sa :" << sa.size() << "\n";
	for (auto i : sa) std::cout << i << ' ';
	std::cout << "\n\n";

	std::cout << "rank :" << rank.size() << "\n";
	for (auto i : rank) std::cout << i << ' ';
	std::cout << "\n\n";

	std::cout << "height :" << height.size() << "\n";
	for (auto i : height) std::cout << i << ' ';
	std::cout << "\n\n";
}

